/*
 * ============================================================================
 *
 *       Filename:  avl.c
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  2014年09月25日 14时48分12秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  jianxi sun (jianxi), ycsunjane@gmail.com
 *   Organization:  
 *
 * ============================================================================
 */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <errno.h>

#include "avl.h"

/* caculate same key times */
int hit = 0;

static void *safe_calloc(size_t nmemb, size_t size)
{
	char *ptr = calloc(nmemb, size);
	if(ptr == NULL) {
		fprintf(stderr, "Malloc mem in avl failed: %s\n", 
			strerror(errno));
		exit(-1);
	}

	return ptr;
}

static void r_rotate(struct node_t **p)
{
	assert(p != NULL && (*p)->lchild != NULL);

	struct node_t *new_p = (*p)->lchild;
	(*p)->lchild = new_p->rchild;
	new_p->rchild = (*p);
	(*p) = new_p;
}

static void l_rotate(struct node_t **p)
{
	assert(p != NULL && (*p)->rchild != NULL);

	struct node_t *new_p = (*p)->rchild;
	(*p)->rchild = new_p->lchild;
	new_p->lchild = (*p);
	(*p) = new_p;
}

void left_balance(struct node_t **node)
{
	struct node_t *left;
	struct node_t *lright;
	left = (*node)->lchild;
	
	switch(left->bf) {
	case LH:
		(*node)->bf = left->bf = EH;
		r_rotate(node);
		break;
	case RH:
		lright = left->rchild;
		switch(lright->bf) {
		case RH:
			left->bf = LH;
			lright->bf = EH;
			(*node)->bf = EH;
			break;
		case LH:
			(*node)->bf = LH;
			left->bf = EH;
			lright->bf = EH;
			break;
		case EH:
			(*node)->bf = EH;
			left->bf = EH;
			break;
		default:
			assert(0);
		}

		/* XXX: can not use right, l_rotate will update ptr */
		l_rotate(&(*node)->lchild);
		r_rotate(node);
		break;
	default:
		assert(0);
	}
}

void right_balance(struct node_t **node)
{
	struct node_t *right;
	struct node_t *rleft;
	right = (*node)->rchild;

	switch(right->bf) {
	case RH:
		(*node)->bf = right->bf = EH;
		l_rotate(node);
		break;
	case LH:
		rleft = right->lchild;

		switch(rleft->bf) {
		case LH:
			right->bf = RH;
			rleft->bf = EH;
			(*node)->bf = EH;
			break;
		case RH:
			(*node)->bf = LH;
			right->bf = EH;
			rleft->bf = EH;
			break;
		case EH:
			(*node)->bf = EH;
			right->bf = EH;
			break;
		default:
			assert(0);
		}

		/* XXX: can not use right, r_rotate will update ptr */
		r_rotate(&((*node)->rchild));
		l_rotate(node);
		break;
	default:
		assert(0);
	}
}

int _insert_node(struct node_t **node, struct node_t *parent, 
	int *bf, int key, void *arg)
{
	assert(node != NULL);

	if( (*node) == NULL ) {
		(*node) = safe_calloc(1, sizeof(struct node_t));
		(*node)->bf = EH;
		(*node)->key = key;
		/* lchild and rchild be NULL*/
		(*node)->arg = arg;

		/* update parent bf */
		if(parent)
			*bf = parent->lchild == (*node) ? LH : RH;
		return 0;
	}

	if( key == (*node)->key ) {
		fprintf(stderr, "key hit:%d \n", hit);
		return -1;
	} else if( key < (*node)->key ) {
		if(_insert_node(&(*node)->lchild, (*node), bf, key, arg) == -1)
			return -1;

		(*node)->bf += *bf;

		if(UNBALANCE((*node)->bf)) {
			left_balance(node);
			*bf = 0;
		}

		/* update parent bf, keep *bf > 0*/
		(*bf) = (*bf) > 0? (*bf) : -(*bf);
		if(parent)
			*bf = parent->lchild == (*node) ? (*bf) : -(*bf);
		return 0;
	} else if( key > (*node)->key ) {
		if(_insert_node(&(*node)->rchild, (*node), bf, key, arg) == -1)
			return -1;

		(*node)->bf += *bf;

		if(UNBALANCE((*node)->bf)) {
			right_balance(node);
			*bf = 0;
		}

		/* update parent bf, keep *bf > 0*/
		(*bf) = (*bf) > 0? (*bf) : -(*bf);
		if(parent)
			*bf = parent->lchild == (*node) ? (*bf) : -(*bf);
		return 0;
	}
}

void _travel_node(struct node_t *node, int height)
{
	assert(node != NULL);
	
	if(node->lchild)
		_travel_node(node->lchild, height+1);
	printf("h: %d, key: %d \n", height, node->key);

	if(node->rchild)
		_travel_node(node->rchild, height+1);
}
